package futu


/*
在由整数组成的数组中，从小到大找出第一个不存在的正整数
用例1：
    输入：[]
    输出: [1]
用例2：
    输入：[-4, 0, 4, 1]
    输出：[2]
用例3：
    输入：[-1, 0, 3, 1, 2, 25]
    输出：[4]
用例4：
    输入：[2, 1, 4, 3]
    输出：[5]
用例5：
    输入：[2, 2, 1, 4]
    输出：[3]
用例6：
    输入：[2, 1]
    输出：[3]
*/
func FindMinNoExist(arr []int) int {
	/*
		方案一： 排序 O(NlogN) + O(N) = O(NlogN)
		方案二： 使用map
				额外空间复杂度：O(N)
				算法复杂度： 转化O(N) + 查找O(N) = O(2N) = O(N)
		最低的算法复杂度 为 O(N)
			因为不可能没看完数组就可以知道答案
	*/
	// 基础防护
	if len(arr) == 0 {
		return 1
	}

	NumMap := make(map[int]bool, len(arr))
	for i := 0; i<len(arr); i++ {
		NumMap[arr[i]] = true
	}

	ans := 1
	for NumMap[ans] {
		ans++
	}
	return ans
}